Public key encryption methods, which are especially important among today's encryption techniques, are widely used for encryption, signature and authentication. An algorithm for realizing a public key cryptosystem generally requires a very high cost of calculation. One of practical methods to realize a public key cryptosystem is an RSA cryptography. The RSA cryptography requires an operation of raising a plaintext or a ciphertext to the power of the number (an encryption exponent or a decryption exponent) obtained from a value of the Eulerian function of n, which is a product of two large prime numbers and then determining the residue of n, and the cost of this operation is very high. In order to enhance the security of a key, the bit number of n is required to be large. However, the cost of calculation required for RSA cryptography with a large bit number is very high. Though measures such as performing such an operation with dedicated hardware may be taken to seek a high speed, this may impose a development and manufacture cost burden or affect product flexibility. Because of such a situation, the cost of a cryptosystem using a public key is high, and it is difficult to incorporate it in an apparatus which is inexpensively mass-produced.
Also known is elliptic-curve cryptography with a smaller bit number and an equivalent strength in comparison with an RSA cryptography. However, though the cost of operations required for encryption (scalar multiplication of a point on an elliptic curve defined on a finite body, and the like) is lower in comparison with that of modulo exponentiation, the cryptography similarly requires expensive operations, and therefore, it is still difficult to incorporate it in an apparatus which is inexpensively mass-produced. Furthermore, there is also proposed a method for realizing a public key cryptosystem with the use of a secret key cryptosystem and tamper-free hardware. In this method, a receiver encrypts his own secret key with a secret key of a third-party body and publishes it. A sender decrypts it with the secret key of a third-party body, encrypts a message with the obtained secret key of the receiver and sends it. The receiver decrypts it with his own secret key. Because encryption with the secret key of the third-party body, decryption with the secret key of the third-party body and encryption with the secret key of the receiver are performed in temper-proof hardware, security is ensured. In this method, however, the sender and the receiver have to use different hardware, and both of their secret keys are required to use the same hardware. This method is similar to an approach such as an ID-based cryptosystem, in which a public key is distributed not via a certification body, in that an ID is published. In this method, a key generation body generates a user's private key from an unique ID of the user, and anyone can generate the user's public key from the user's ID. This method is convenient with regard to distribution of a public key. However, the nature of the trap-door one-way function in the RSA cryptography and the like is utilized for encryption-decryption of a message, and the cost required for the processing is as high as that of common public key cryptosystems.    Patent Document 1 Published Unexamined Patent Application No. 2004-70712